home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 98 / Skunkware 98.iso / src / mail / db.1.85.tar.gz / db.1.85.tar / db.1.85 / btree / bt_open.c < prev    next >
C/C++ Source or Header  |  1994-08-18  |  11KB  |  445 lines
  1. /*-
  2.  * Copyright (c) 1990, 1993, 1994
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)bt_open.c    8.10 (Berkeley) 8/17/94";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. /*
  42.  * Implementation of btree access method for 4.4BSD.
  43.  *
  44.  * The design here was originally based on that of the btree access method
  45.  * used in the Postgres database system at UC Berkeley.  This implementation
  46.  * is wholly independent of the Postgres code.
  47.  */
  48.  
  49. #include <sys/param.h>
  50. #include <sys/stat.h>
  51.  
  52. #include <errno.h>
  53. #include <fcntl.h>
  54. #include <limits.h>
  55. #include <signal.h>
  56. #include <stdio.h>
  57. #include <stdlib.h>
  58. #include <string.h>
  59. #include <unistd.h>
  60.  
  61. #include <db.h>
  62. #include "btree.h"
  63.  
  64. #ifdef DEBUG
  65. #undef    MINPSIZE
  66. #define    MINPSIZE    128
  67. #endif
  68.  
  69. static int byteorder __P((void));
  70. static int nroot __P((BTREE *));
  71. static int tmp __P((void));
  72.  
  73. /*
  74.  * __BT_OPEN -- Open a btree.
  75.  *
  76.  * Creates and fills a DB struct, and calls the routine that actually
  77.  * opens the btree.
  78.  *
  79.  * Parameters:
  80.  *    fname:    filename (NULL for in-memory trees)
  81.  *    flags:    open flag bits
  82.  *    mode:    open permission bits
  83.  *    b:    BTREEINFO pointer
  84.  *
  85.  * Returns:
  86.  *    NULL on failure, pointer to DB on success.
  87.  *
  88.  */
  89. DB *
  90. __bt_open(fname, flags, mode, openinfo, dflags)
  91.     const char *fname;
  92.     int flags, mode, dflags;
  93.     const BTREEINFO *openinfo;
  94. {
  95.     struct stat sb;
  96.     BTMETA m;
  97.     BTREE *t;
  98.     BTREEINFO b;
  99.     DB *dbp;
  100.     pgno_t ncache;
  101.     ssize_t nr;
  102.     int machine_lorder;
  103.  
  104.     t = NULL;
  105.  
  106.     /*
  107.      * Intention is to make sure all of the user's selections are okay
  108.      * here and then use them without checking.  Can't be complete, since
  109.      * we don't know the right page size, lorder or flags until the backing
  110.      * file is opened.  Also, the file's page size can cause the cachesize
  111.      * to change.
  112.      */
  113.     machine_lorder = byteorder();
  114.     if (openinfo) {
  115.         b = *openinfo;
  116.  
  117.         /* Flags: R_DUP. */
  118.         if (b.flags & ~(R_DUP))
  119.             goto einval;
  120.  
  121.         /*
  122.          * Page size must be indx_t aligned and >= MINPSIZE.  Default
  123.          * page size is set farther on, based on the underlying file
  124.          * transfer size.
  125.          */
  126.         if (b.psize &&
  127.             (b.psize < MINPSIZE || b.psize > MAX_PAGE_OFFSET + 1 ||
  128.             b.psize & sizeof(indx_t) - 1))
  129.             goto einval;
  130.  
  131.         /* Minimum number of keys per page; absolute minimum is 2. */
  132.         if (b.minkeypage) {
  133.             if (b.minkeypage < 2)
  134.                 goto einval;
  135.         } else
  136.             b.minkeypage = DEFMINKEYPAGE;
  137.  
  138.         /* If no comparison, use default comparison and prefix. */
  139.         if (b.compare == NULL) {
  140.             b.compare = __bt_defcmp;
  141.             if (b.prefix == NULL)
  142.                 b.prefix = __bt_defpfx;
  143.         }
  144.  
  145.         if (b.lorder == 0)
  146.             b.lorder = machine_lorder;
  147.     } else {
  148.         b.compare = __bt_defcmp;
  149.         b.cachesize = 0;
  150.         b.flags = 0;
  151.         b.lorder = machine_lorder;
  152.         b.minkeypage = DEFMINKEYPAGE;
  153.         b.prefix = __bt_defpfx;
  154.         b.psize = 0;
  155.     }
  156.  
  157.     /* Check for the ubiquitous PDP-11. */
  158.     if (b.lorder != BIG_ENDIAN && b.lorder != LITTLE_ENDIAN)
  159.         goto einval;
  160.  
  161.     /* Allocate and initialize DB and BTREE structures. */
  162.     if ((t = (BTREE *)malloc(sizeof(BTREE))) == NULL)
  163.         goto err;
  164.     memset(t, 0, sizeof(BTREE));
  165.     t->bt_fd = -1;            /* Don't close unopened fd on error. */
  166.     t->bt_lorder = b.lorder;
  167.     t->bt_order = NOT;
  168.     t->bt_cmp = b.compare;
  169.     t->bt_pfx = b.prefix;
  170.     t->bt_rfd = -1;
  171.  
  172.     if ((t->bt_dbp = dbp = (DB *)malloc(sizeof(DB))) == NULL)
  173.         goto err;
  174.     memset(t->bt_dbp, 0, sizeof(DB));
  175.     if (t->bt_lorder != machine_lorder)
  176.         F_SET(t, B_NEEDSWAP);
  177.  
  178.     dbp->type = DB_BTREE;
  179.     dbp->internal = t;
  180.     dbp->close = __bt_close;
  181.     dbp->del = __bt_delete;
  182.     dbp->fd = __bt_fd;
  183.     dbp->get = __bt_get;
  184.     dbp->put = __bt_put;
  185.     dbp->seq = __bt_seq;
  186.     dbp->sync = __bt_sync;
  187.  
  188.     /*
  189.      * If no file name was supplied, this is an in-memory btree and we
  190.      * open a backing temporary file.  Otherwise, it's a disk-based tree.
  191.      */
  192.     if (fname) {
  193.         switch (flags & O_ACCMODE) {
  194.         case O_RDONLY:
  195.             F_SET(t, B_RDONLY);
  196.             break;
  197.         case O_RDWR:
  198.             break;
  199.         case O_WRONLY:
  200.         default:
  201.             goto einval;
  202.         }
  203.         
  204.         if ((t->bt_fd = open(fname, flags, mode)) < 0)
  205.             goto err;
  206.  
  207.     } else {
  208.         if ((flags & O_ACCMODE) != O_RDWR)
  209.             goto einval;
  210.         if ((t->bt_fd = tmp()) == -1)
  211.             goto err;
  212.         F_SET(t, B_INMEM);
  213.     }
  214.  
  215.     if (fcntl(t->bt_fd, F_SETFD, 1) == -1)
  216.         goto err;
  217.  
  218.     if (fstat(t->bt_fd, &sb))
  219.         goto err;
  220.     if (sb.st_size) {
  221.         if ((nr = read(t->bt_fd, &m, sizeof(BTMETA))) < 0)
  222.             goto err;
  223.         if (nr != sizeof(BTMETA))
  224.             goto eftype;
  225.  
  226.         /*
  227.          * Read in the meta-data.  This can change the notion of what
  228.          * the lorder, page size and flags are, and, when the page size
  229.          * changes, the cachesize value can change too.  If the user
  230.          * specified the wrong byte order for an existing database, we
  231.          * don't bother to return an error, we just clear the NEEDSWAP
  232.          * bit.
  233.          */
  234.         if (m.magic == BTREEMAGIC)
  235.             F_CLR(t, B_NEEDSWAP);
  236.         else {
  237.             F_SET(t, B_NEEDSWAP);
  238.             M_32_SWAP(m.magic);
  239.             M_32_SWAP(m.version);
  240.             M_32_SWAP(m.psize);
  241.             M_32_SWAP(m.free);
  242.             M_32_SWAP(m.nrecs);
  243.             M_32_SWAP(m.flags);
  244.         }
  245.         if (m.magic != BTREEMAGIC || m.version != BTREEVERSION)
  246.             goto eftype;
  247.         if (m.psize < MINPSIZE || m.psize > MAX_PAGE_OFFSET + 1 ||
  248.             m.psize & sizeof(indx_t) - 1)
  249.             goto eftype;
  250.         if (m.flags & ~SAVEMETA)
  251.             goto eftype;
  252.         b.psize = m.psize;
  253.         F_SET(t, m.flags);
  254.         t->bt_free = m.free;
  255.         t->bt_nrecs = m.nrecs;
  256.     } else {
  257.         /*
  258.          * Set the page size to the best value for I/O to this file.
  259.          * Don't overflow the page offset type.
  260.          */
  261.         if (b.psize == 0) {
  262.             b.psize = sb.st_blksize;
  263.             if (b.psize < MINPSIZE)
  264.                 b.psize = MINPSIZE;
  265.             if (b.psize > MAX_PAGE_OFFSET + 1)
  266.                 b.psize = MAX_PAGE_OFFSET + 1;
  267.         }
  268.  
  269.         /* Set flag if duplicates permitted. */
  270.         if (!(b.flags & R_DUP))
  271.             F_SET(t, B_NODUPS);
  272.  
  273.         t->bt_free = P_INVALID;
  274.         t->bt_nrecs = 0;
  275.         F_SET(t, B_METADIRTY);
  276.     }
  277.  
  278.     t->bt_psize = b.psize;
  279.  
  280.     /* Set the cache size; must be a multiple of the page size. */
  281.     if (b.cachesize && b.cachesize & b.psize - 1)
  282.         b.cachesize += (~b.cachesize & b.psize - 1) + 1;
  283.     if (b.cachesize < b.psize * MINCACHE)
  284.         b.cachesize = b.psize * MINCACHE;
  285.  
  286.     /* Calculate number of pages to cache. */
  287.     ncache = (b.cachesize + t->bt_psize - 1) / t->bt_psize;
  288.  
  289.     /*
  290.      * The btree data structure requires that at least two keys can fit on
  291.      * a page, but other than that there's no fixed requirement.  The user
  292.      * specified a minimum number per page, and we translated that into the
  293.      * number of bytes a key/data pair can use before being placed on an
  294.      * overflow page.  This calculation includes the page header, the size
  295.      * of the index referencing the leaf item and the size of the leaf item
  296.      * structure.  Also, don't let the user specify a minkeypage such that
  297.      * a key/data pair won't fit even if both key and data are on overflow
  298.      * pages.
  299.      */
  300.     t->bt_ovflsize = (t->bt_psize - BTDATAOFF) / b.minkeypage -
  301.         (sizeof(indx_t) + NBLEAFDBT(0, 0));
  302.     if (t->bt_ovflsize < NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t))
  303.         t->bt_ovflsize =
  304.             NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t);
  305.  
  306.     /* Initialize the buffer pool. */
  307.     if ((t->bt_mp =
  308.         mpool_open(NULL, t->bt_fd, t->bt_psize, ncache)) == NULL)
  309.         goto err;
  310.     if (!F_ISSET(t, B_INMEM))
  311.         mpool_filter(t->bt_mp, __bt_pgin, __bt_pgout, t);
  312.  
  313.     /* Create a root page if new tree. */
  314.     if (nroot(t) == RET_ERROR)
  315.         goto err;
  316.  
  317.     /* Global flags. */
  318.     if (dflags & DB_LOCK)
  319.         F_SET(t, B_DB_LOCK);
  320.     if (dflags & DB_SHMEM)
  321.         F_SET(t, B_DB_SHMEM);
  322.     if (dflags & DB_TXN)
  323.         F_SET(t, B_DB_TXN);
  324.  
  325.     return (dbp);
  326.  
  327. einval:    errno = EINVAL;
  328.     goto err;
  329.  
  330. eftype:    errno = EFTYPE;
  331.     goto err;
  332.  
  333. err:    if (t) {
  334.         if (t->bt_dbp)
  335.             free(t->bt_dbp);
  336.         if (t->bt_fd != -1)
  337.             (void)close(t->bt_fd);
  338.         free(t);
  339.     }
  340.     return (NULL);
  341. }
  342.  
  343. /*
  344.  * NROOT -- Create the root of a new tree.
  345.  *
  346.  * Parameters:
  347.  *    t:    tree
  348.  *
  349.  * Returns:
  350.  *    RET_ERROR, RET_SUCCESS
  351.  */
  352. static int
  353. nroot(t)
  354.     BTREE *t;
  355. {
  356.     PAGE *meta, *root;
  357.     pgno_t npg;
  358.  
  359.     if ((meta = mpool_get(t->bt_mp, 0, 0)) != NULL) {
  360.         mpool_put(t->bt_mp, meta, 0);
  361.         return (RET_SUCCESS);
  362.     }
  363.     if (errno != EINVAL)        /* It's OK to not exist. */
  364.         return (RET_ERROR);
  365.     errno = 0;
  366.  
  367.     if ((meta = mpool_new(t->bt_mp, &npg)) == NULL)
  368.         return (RET_ERROR);
  369.  
  370.     if ((root = mpool_new(t->bt_mp, &npg)) == NULL)
  371.         return (RET_ERROR);
  372.  
  373.     if (npg != P_ROOT)
  374.         return (RET_ERROR);
  375.     root->pgno = npg;
  376.     root->prevpg = root->nextpg = P_INVALID;
  377.     root->lower = BTDATAOFF;
  378.     root->upper = t->bt_psize;
  379.     root->flags = P_BLEAF;
  380.     memset(meta, 0, t->bt_psize);
  381.     mpool_put(t->bt_mp, meta, MPOOL_DIRTY);
  382.     mpool_put(t->bt_mp, root, MPOOL_DIRTY);
  383.     return (RET_SUCCESS);
  384. }
  385.  
  386. static int
  387. tmp()
  388. {
  389.     sigset_t set, oset;
  390.     int fd;
  391.     char *envtmp;
  392.     char path[MAXPATHLEN];
  393.  
  394.     envtmp = getenv("TMPDIR");
  395.     (void)snprintf(path,
  396.         sizeof(path), "%s/bt.XXXXXX", envtmp ? envtmp : "/tmp");
  397.  
  398.     (void)sigfillset(&set);
  399.     (void)sigprocmask(SIG_BLOCK, &set, &oset);
  400.     if ((fd = mkstemp(path)) != -1)
  401.         (void)unlink(path);
  402.     (void)sigprocmask(SIG_SETMASK, &oset, NULL);
  403.     return(fd);
  404. }
  405.  
  406. static int
  407. byteorder()
  408. {
  409.     u_int32_t x;
  410.     u_char *p;
  411.  
  412.     x = 0x01020304;
  413.     p = (u_char *)&x;
  414.     switch (*p) {
  415.     case 1:
  416.         return (BIG_ENDIAN);
  417.     case 4:
  418.         return (LITTLE_ENDIAN);
  419.     default:
  420.         return (0);
  421.     }
  422. }
  423.  
  424. int
  425. __bt_fd(dbp)
  426.         const DB *dbp;
  427. {
  428.     BTREE *t;
  429.  
  430.     t = dbp->internal;
  431.  
  432.     /* Toss any page pinned across calls. */
  433.     if (t->bt_pinned != NULL) {
  434.         mpool_put(t->bt_mp, t->bt_pinned, 0);
  435.         t->bt_pinned = NULL;
  436.     }
  437.  
  438.     /* In-memory database can't have a file descriptor. */
  439.     if (F_ISSET(t, B_INMEM)) {
  440.         errno = ENOENT;
  441.         return (-1);
  442.     }
  443.     return (t->bt_fd);
  444. }
  445.